import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LIUYANJIAO
 * Date: 2024-10-27
 * Time: 8:57
 */
public class Main {
    //二叉树的层序遍历||
    //递归 子问题
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

    }


    public static String tree2str2(TreeNode root) {
    //子问题
        if(root==null){
            return "";
        }
        if(root.left==null&&root.right==null){
            return Integer.toString(root.val);
        }
        if(root.right==null){
            return new StringBuilder().append(root.val).append("(").append(tree2str2(root.left)).append(")").toString();
        }

        return new StringBuilder().append(root.val).append("(").append(tree2str2(root.left)).
                append(")(").append(root.right).append(")").toString();
    }
    public static String tree2str3(TreeNode root){
        StringBuilder stringBuilder=new StringBuilder();
        String s=tree1str(root,stringBuilder);
        stringBuilder= new StringBuilder(s);

        String[] split = s.split("\\(\\)");
        List<String> list=new ArrayList<>(List.of(split));
        String ret=list.get(0);
        for (int i = 1; i < list.size(); i++) {
            if(!(list.get(i).equals(""))&&list.get(i).charAt(0)!=')'){
                list.add(i,"()");
                ret+=list.get(i);
                i++;

            }
            ret+=list.get(i);
        }



        return ret;
    }
    public static String tree1str(TreeNode root,StringBuilder stringBuilder) {


        if(root==null) {

            return stringBuilder.toString();
        }

        stringBuilder.append(root.val);

        stringBuilder.append("(");
        tree1str(root.left, stringBuilder);
        stringBuilder.append(")");

        stringBuilder.append("(");
        tree1str(root.right,stringBuilder);
        stringBuilder.append(")");

        return stringBuilder.toString();

    }

    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        Deque<TreeNode> deque=new ArrayDeque<>();
        while(root!=null||!deque.isEmpty()){
            if(deque.isEmpty()){
                deque.push(root);
            }
            int size=deque.size();
            List<Integer> list=new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode t=new TreeNode(deque.pop().val);
                list.add(t.val);

                if(root.left!=null) deque.offer(root.left);
                if(root.right!=null) deque.offer(root.right);

                root=deque.peek();
            }
            ret.add(0,list);
        }
        return ret;


    }
    public static void main(String[] args) {
        TreeNode a=new TreeNode(1);
        TreeNode b=new TreeNode(2);
        TreeNode c=new TreeNode(3);
        TreeNode d=new TreeNode(4);

        a.left=b;
        a.right=c;

        b.right=d;
        StringBuilder stringBuilder=new StringBuilder();

        System.out.println(tree2str(a));

    }
}